Куркчи Вячеслав Андреевич
kourktchi@ukrtop.com
магистрант группы ПО-99, ФВТИ
научный руководитель:
Ладыженский Юрий Валентинович

тема магистерской работы:
Параллельные алгоритмы для решения задач на графах.

     Для определения распространненности исследуемой темы, было проведено следующее исследование: ряду популярных поисковых сайтов в Интернет был дан ряд запросов и зафиксировано количество найденных сайтов по запросу сайтов.
     Резутьтаты были сведены в таблицу.

     Данные на 19.03.2004

Запрос	Google	Rambler	Yandex	Meta-Ukraine
Теория графов	6210	11448	14138	1600
Задача о наибольшем независимом множестве	1	10346	43	1993
Задача о наибольшей клике	34	10346	98	117
Параллельные алгоритмы	4430	14044	702	2503
Параллельные алгоритмы на графах	191	1948	171	211
Graph theory	2020000	1774	2407	147
Maximum independent set	2520000	4763	77	1071
Maximum clique problem	31500	94	736	12
Parallel algorithms	1860000	3056	508	417
Parallel algorithms for graphs	227000	684	47	64
Neuro networks for graph theory	6760	41	90	7
Tabu search for graph theory	6760	10	730	0
Genetic algorithms for graph theory	49600	175	159	7
Greedy heuristic for graph theory	14800	15	133	0
Simulated annealing for graph theory	20600	85	636	5
NP-complete problems	121000	597	123	22
NP-completeness in graph theory	23300	68	44	1

     Из таблицы видно, что русскоязычные запросы лучше всего обрабатываются поисковым сервером Rambler, а англоязычные - Google (разумеется, среди рассмотренных). Также можно увидеть, что англоязычный Интернет содержит на несколько порядков больше страниц, содержащих ключевые слова по теме.
     Следует отметить, что "страницы, содержащие ключевые слова по теме" еще не значит "страницы на тему", так как слово граф имеет не одно значение в русском языке, а слово graph - еще больше значений в английском (причем не только как имя существительное, но и как глагол). Это во многом применимо и к другим словам, использованным в запросах. Следовательно, большое число страниц, содержащих искомые ключевые слова, может свидетельствовать как о более обширном представлении темы, так и о большей засоренности информационного пространства.
     Проверить какое из этих утверждений правильное не представляется возможным, так как обработать даже краткое описание нескольких сотен тысяч страницы достаточно трудоемко. Но в силу того, что количество страниц-ответов на запросы с большим количеством ключевых слов или более специальные запросы оказалось в среднем на 2-3 порядка меньше, более вероятной кажется версия о засоренности. С другой стороны, графы представляют собой весьма распространенные структуру данных и математический аппарат, используемые во многих областях науки и техники. Но такая поразительная разница в числах вызывает некоторые сомнения в том, что это может быть причиной наблюдаемого явления.

     Вновь затрагивая тему сравнения поисковых сайтов, отметим, что количественные оценки результатов Rambler и Yandex колеблются относительно друг друга. Причем эти колебания не зависят ни от темы, ни от степени ее специализации. Единственный вывод, который можно сделать в данном случае: для повышения вероятности найти необходимую информацию следует параллельно использовать оба сайта.
     Meta-Ukraine является "молодым" сайтом, но уже может составить конкуренцию остальным рассматриваемым поисковым серверам, правда в ограниченном круге тем.

     Для рассмотрения изменения распространенности темы было проведено повторное исследование.

     Данные на 1.06.2004

Запрос	Google	Rambler	Yandex	Meta-Ukraine
Теория графов	6020	67742	15809	1840
Задача о наибольшем независимом множестве	7	58601	192	2004
Задача о наибольшей клике	32	4664	190	136
Параллельные алгоритмы	4090	76161	8047	2554
Параллельные алгоритмы на графах	174	6380	192	242
Graph theory	2330000	8170	2587	127
Maximum independent set	2580000	31932	78	716
Maximum clique problem	31400	237	8853	6
Parallel algorithms	1650000	19246	3591	286
Parallel algorithms for graphs	256000	3347	108	56
Neuro networks for graph theory	8740	54	159	1
Tabu search for graph theory	7480	123	11561	0
Genetic algorithms for graph theory	61000	334	502	3
Greedy heuristic for graph theory	15000	14	347	0
Simulated annealing for graph theory	21600	100	9184	3
NP-complete problems	111000	1701	446	8
NP-completeness in graph theory	22600	90	152	1

     При сравнении таблиц видно, что ситуация в англоязычной части таблицы в целом не изменилась: результаты некоторых стали больше, других - меньше, но большинство этих изменений несущественны, так как они не превышают 10%. Но некоторые темы все-таки набирают популярность, это генетические алгоритмы, нейросети и поиск табу. (за условный показатель популярности темы был принят максимум по запросу: по поисковым серверам). Эти темы действительно считаются приоритетными направлениями исследований и развиваются очень быстро. В русскоязычном Интернете можно отметить значительный рост популярности.
     Также сильно изменилось поведение сайтов: усилились позиции Rambler, и расширился англоязычный поиск Yandex. Результаты поиска Meta-Ukraine практически не отличаются.

     В заключение можно сказать, что при поиске в Интернете англоязычной информации по рассматриваемой теме следует использовать Google, и при поиске русскоязычной - Rambler. Yandex и Meta-Ukraine использовать нецелесообразно, несмотря на то, что Yandex в период между экспериментами провел переиндексацию ресурсов Интернет. Возможно, руководство Yandex, считает более приоритетными другие темы.

Вернуться к началу